package main

import "fmt"

func main() {
	adjacentPairs := [][]int{
		{2, 1}, {3, 4}, {3, 2},
	}
	fmt.Println(restoreArray(adjacentPairs))
}

//#link: https://leetcode-cn.com/problems/restore-the-array-from-adjacent-pairs/
func restoreArray(adjacentPairs [][]int) []int {
	tmpMap := make(map[int][]int)
	for _, v := range adjacentPairs {
		tmpMap[v[0]] = append(tmpMap[v[0]], v[1])
		tmpMap[v[1]] = append(tmpMap[v[1]], v[0])
	}
	n := len(adjacentPairs) + 1
	ans := make([]int, n)
	//找到第一个节点
	for e, adj := range tmpMap {
		if len(adj) == 1 {
			ans[0] = e
			break
		}
	}

	//从第一个节点开始找相邻节点
	ans[1] = tmpMap[ans[0]][0]
	for i := 2; i < n; i++ {
		adj := tmpMap[ans[i-1]]
		//找未存在的节点
		if ans[i-2] == adj[0] {
			ans[i] = adj[1]
		} else {
			ans[i] = adj[0]
		}
	}
	return ans
}
